package day003;

// 满二叉树
public class Code04_IsFBT {
    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public static boolean check(Node head){
        if(head == null){
            return true;
        }
        ReturnData res = isFBT(head);
        System.out.println(res.height+"  "+ res.nodeNums);
        System.out.println((1 << res.height) - 1);
        return res.nodeNums == (Math.pow(2,res.height) - 1);
    }


    public static ReturnData isFBT(Node head){
        if(head == null){
            return new ReturnData(0,0);
        }

        ReturnData lData = isFBT(head.left);
        ReturnData rData = isFBT(head.right);

        int height = Math.max(lData.height, rData.height) + 1;
        int nodeNums = lData.nodeNums + rData.nodeNums + 1;

        return new ReturnData(height, nodeNums);
    }

    public static class ReturnData{
        public int height;
        public int nodeNums;

        public ReturnData(int height, int nodeNums) {
            this.height = height;
            this.nodeNums = nodeNums;
        }
    }

    public static void main(String[] args) {
        Node n7 = new Node(7);
        Node n6 = new Node(6);
        Node n5 = new Node(5);
        Node n4 = new Node(4);
        Node n3 = new Node(3,n6,n7);
        Node n2 = new Node(2,n4, n5);
        Node n1 = new Node(1,n2,n3);

        System.out.println(check(n1));
    }
}
